package com.example.demo.algorithms;

import org.junit.jupiter.api.Test;

import java.util.Comparator;
import java.util.PriorityQueue;

/**
 * <p>Description: 最k小（大）个数</p>
 *
 * @author Eric Lee
 * @version v1.0.0
 * @since 2021/2/27 15:17
 **/
public class SmallestK {

    @Test
    public void test() {
//        int[] a = {100, 88, 44, 66, 77, 11, 22, 5, 55};
//        int[] result = {100, 88, 66, 77, 55};

        int[] a = {2, 77, 44, 66, 88, 11, 22, 5, 55, 100};
        int[] b = biggestK(a, 3);
        System.out.println(b);
    }


    public PriorityQueue<Integer> buildMaxHeap(int[] array) {
        PriorityQueue<Integer> maxHeap = new PriorityQueue<>();
        for (int item : array) {
            maxHeap.add(item);
        }
        return maxHeap;
    }

    // k个最小值
    public int[] smallestK(int[] arr, int k) {
        int[] vec = new int[k];
        if (k == 0) { // 排除 0 的情况
            return vec;
        }
        PriorityQueue<Integer> maxHeap = new PriorityQueue<Integer>(new Comparator<Integer>() {
            public int compare(Integer num1, Integer num2) {
                return num2 - num1;         // 最大堆比较器
            }
        });
        for (int i = 0; i < k; ++i) {
            maxHeap.offer(arr[i]);
        }
        for (int i = k; i < arr.length; ++i) {
            if (maxHeap.peek() > arr[i]) {
                maxHeap.poll();
                maxHeap.offer(arr[i]);
            }
        }
        for (int i = 0; i < k; ++i) {
            vec[i] = maxHeap.poll();
        }
        return vec;
    }

    // 最k大个数
    public int[] biggestK(int[] A, int k) {
        int[] result = new int[k];
        if (k == 0) { // 排除 0 的情况
            return result;
        }
        int count = 0;
        PriorityQueue<Integer> minHeap = new PriorityQueue<Integer>();    // 由大堆的前k个元素组成的最小堆
        for (int i = 0; i < k; ++i) {
            // 从最大堆中取前k个，形成对小堆
            minHeap.add(A[i]);   //入堆
        }
        int minHeapRootValue = minHeap.peek();
        for (int i = k; i < A.length; ++i) {
            if (minHeapRootValue < A[i]) {    // 小堆中的顶点（最小值） 与 剩余数组中的值比较，如果剩余数组中有更大的，则小堆出堆，让更大的入堆。
                minHeap.poll();           // 从最小堆中删除更小的值
                minHeap.add(A[i]);    // 将更大的值插入最小堆
                count++;
            }
        }
        for (int i = k - 1; i >= 0; --i) {
            result[i] = minHeap.poll();     // 逆序取出小堆元素，即构成n个元素中的前k个最大值数组
        }
        return result;
    }


}
